Fedyuninsky sinh ra trong một gia đình nông dân gần Tugulym ở Urals. Ông học xong trường làng năm 1913 và học nghề họa sĩ trang trí. Ông gia nhập Hồng quân năm 1919 và từng chiến đấu ở Mặt trận phía Tây trong Nội chiến Nga và bị thương hai lần.

Ông học tại Trường Bộ binh Vladivostok từ năm 1923–1924 và được bổ nhiệm vào một trung đoàn bộ binh. Ông phục vụ ở vùng Viễn Đông của Nga từ năm 1919 đến năm 1940, tham chiến trong cuộc xung đột Trung-Xô 1929 và là chỉ huy của Trung đoàn cơ giới 24 trong Chiến dịch Khalkhyn Gol, nơi ông có được danh hiệu Anh hùng Liên Xô vì lòng dũng cảm của mình. Ông được thăng cấp Sư đoàn trưởng (komdiv) năm 1940, chỉ huy Sư đoàn súng trường 82, sau này là sư đoàn súng trường cơ giới.

Ông chỉ huy Quân đoàn súng trường 15 trong Tập đoàn quân 5 vào ngày 22 tháng 6 năm 1941. Sau đó, ông lần lượt trải qua các chức vụ chỉ huy khác, bao gồm chỉ huy các Tập đoàn quân 54[1] và 42 tại Leningrad,[2] Tập đoàn quân xung kích 2 ngay trước Trận chiến Narva (1944). Ông được thăng cấp trung tướng vào ngày 11 tháng 7 năm 1945.[3]

Từ năm 1946 đến năm 1951, ông chỉ huy Tập đoàn quân Cận vệ 7.[4] Trong những năm sau đó, ông là là phó chỉ huy của Cụm binh đoàn Liên Xô tại Đức (1951–1954), chỉ huy các Quân khu Zakavkaz (1954–1957) và Turkestan (1957–1965). Ông được thăng quân hàm Đại tướng năm 1955 và là thanh tra kiêm cố vấn của Bộ Quốc phòng Liên Xô từ năm 1965 cho đến khi qua đời. Ông cũng từng được bầu làm Phó chủ tịch của Xô viết Tối cao Liên Xô.

Ivan Fedyuninsky đã được tặng thưởng 4 Huân chương của Lenin, 5 Huân chương Đỏ, 2 Huân chương Suvorov (Hạng 1 và 2), 2 Huân chương Kutuzov, Huân chương Sao Đỏ, Huân chương Phục vụ Tổ quốc trong Lực lượng vũ trang của Liên Xô (Hạng 3), nhiều huy chương, và một số đơn đặt hàng và huy chương nước ngoài.